---
title: 并发容器
---

## 同步容器
Java 中的容器主要可以分为四个大类，分别是 List、Set、Map 和 Queue。

如何将非线程安全的容器编程线程安全的容器，其实思路很简单那，只要把非线程安全的容器封装在对象内部，然后控制好访问路径就可以了。

下面以 ArrayList 为例，将它变成线程安全的。

```java
public class SafeArrayList <T>{
    //封装 ArrayList
    List<T> c = new ArrayList<>();

    //控制访问路径
    synchronized T get(int idx) {
        return c.get(idx);
    }

    synchronized void add(T t) {
        c.add(t);
    }

    synchronized boolean addIfNotExist(T t) {
        if (!c.contains(t)) {
            c.add(t);
            return true;
        }
        return false;
    }
}

```
非线程安全的类都可以用这种包装的方式来实现线程安全， Collections 这个类中提供了一套完备的包装类，可以分别把 ArrayList、HashSet 和 HashMap 包装成了线程安全的 List、Set 和 Map。

```java
    List list = Collections.synchronizedList(new ArrayList<>());
    Set set = Collections.synchronizedSet(new HashSet<>());
    Map map = Collections.synchronizedMap(new HashMap<>());
```
组合操作需要注意竞态条件问题，例如上面提到的 addIfNotExist() 方法就是包含组合操作。组合操作往往隐藏着竞态条件问题，即使每个操作都能保证原子性，也不能保证组合操作的原子性。

在容器领域一个容易被忽视的“坑”是用迭代器遍历容器，例如在下面的代码中，通过迭代器遍历容器 list，对每个元素调用 foo() 方法，这就存在并发操作，这些组合操作不具备原子性。

```java
List list = Collections.synchronizedList(new ArrayList<>());
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    foo(iterator.next());
}
```

正确的做法应该是，锁住 list之后再进行遍历操作

上面提高的这些包装过的 线程安全容器，都是基于 synchronized 这个同步关键字实现的，所以也被称为同步容器。Java 提供的同步容器还有 Vector、Stack 和 HashTable。

## 并发容器
同步容器都是通过 synchronized 来保证互斥，串行度太高了。因此 Java 在 1.5 之后版本提供了性能更高的容器，一般称为**并发容器**。

并发容器的数量虽然非常多，但依然是四大类：List、Set、Map 和 Queue。如下图：

![](https://img.wkq.pub/pic/a20efe788caf4f07a4ad027639c80b1d.webp)

### 1. List

List 里面只有一个实现类就是 **CopyOnWriteArrayList**。CopyOnWrite，顾名思义就是写的时候会将共享变量新复制一份出来，这样做的好处是读操作完全无锁。

CopyOnWriteArrayList 内部维护了一个数组，成员变量 array 就指向这个内部数组，所有的读操作都是基于 array 进行的，如下图所示：迭代器 Iterator 遍历的就是 array 数组。

![38739130ee9f34b821b5849f4f15e710](https://img.wkq.pub/pic/38739130ee9f34b821b5849f4f15e710.webp)

如果在 遍历 array 的同时，还有一个写操作，例如增加元素， CopyOnWriteArrayList 会将 array 复制一份，然后在新复制的数组上执行增加元素的操作，执行完之后再将 array 指向这个新的数组。

如下图所示，读写是可以并行的，遍历操作一直都是基于原 array 执行，而写操作则是基于新 array 进行。



![b861fb667e94c4e6ea0ca9985e63c889](https://img.wkq.pub/pic/b861fb667e94c4e6ea0ca9985e63c889.webp)

1. CopyOnWriteArrayList 仅仅适用于写操作非常少的场景，而且能够容忍读写的短暂不一致。
2. CopyOnWriteArrayList 的迭代器是只读的，不支持增删改，因为迭代器遍历的仅仅是一个快照，而对快照进行增删改是没有意义的。

### 2. Map

Map 接口的两个实现是 ConcurrentHashMap 和 ConcurrentSkipListMap ，主要区别在于 **ConcurrentHashMap 的 key 是无序的，而 ConcurrentSkipListMap 的key 是有序的**。如果需要保证 key 的顺序，就只能使用 ConcurrentSkipListMap。

它们的 key 和 value 都不能为空，否则会抛出 NullPointerException 这个 运行时异常。

**ConcurrentHashMap 利用分段锁和CAS实现线程安全，同时使用读写锁提高并发性能。**

![6da9933b6312acf3445f736262425abe (1)](https://img.wkq.pub/pic/6da9933b6312acf3445f736262425abe%20(1).webp)

ConcurrentSkipListMap 里面的 SkipMap 本身就是一种数据结构，中文一般都翻译为跳表，跳表插入、删除、查询平均时间复杂度是 O(logn)

### 3. Set

Set 接口的两个实现是 CopyOnWriteArraySet 和 ConcurrentSkipListSet ，使用场景可以参考 CopyOnWriteArrayList 和 ConcurrentSkipListMap。

### 4. Queue

Queue 可以从以下两个维度来分类。



一个维度是**阻塞和非阻塞**，所谓阻塞指的是当队列已满时，入队操作阻塞；当队列已空时，出队操作阻塞。

另一个维度是**单端与双端**，单端指的是只能在队尾入队，队首出队；而双端指的是队首对位皆可以入队出队。



**Java 并发包里的阻塞队列都用 Blocking 关键字标识**，**单端队列使用 Queue 标识，双端队列使用 Deque标识**。



这两个维度组合后，可以将 Queue 细分为四大类，分别是：

1. **单端阻塞队列**：其实现有 ArrayBlockingQueue、LinkedBlockingQueue、SynchronousQueue、LinkedTransferQueue、PriorityBlockingQueue 和 DelayQueue。内部一般会持有一个队列，这个队列可以是数组（其实现是 ArrayBlockingQueue）,也可以是链表（其实现是 LinkedBlockingQueue），甚至是还可以不持有队列（其实现是 SynchronousQueue），此时生产者线程的入队操作必须等待消费者队列的出队操作。而 LinkedTransferQueue 融合了 LinkedBlockQueue 和 SynchronousQueue 的功能，性能比 LinedBlockQueue 更好；PriorityBlockQueue 支持按照优先级出队；DelayQueue 支持延时出队。

![5974a10f5eb0646fa94f7ba505bfcf83](https://img.wkq.pub/pic/5974a10f5eb0646fa94f7ba505bfcf83.webp)

2. **双端阻塞队列**： 其实现是 LinkedBlockDeque
3. **单端非阻塞队列**: 其实现是 ConcurrentLinkedQueue
4. **双端非阻塞队列**: ConcurrentLinkedDeque

另外，使用队列时，需要格外注意队列是否支持有界（所谓有界指的是内部的队列是否有容量限制）。

在工作中，一般不建议使用无界的队列，因为数据量大了之后容易导致 OOM  异常。

:::tip

这里的有界，是指生成队列的时候，在构造函数中指定队列的大小；如果不指定，则认为是无界的，实际上，即使调用了无界的构造函数，其队列的大小就是Integer.MAX_VALUE

:::

